    package com.dycong.common.dataStructuresAndAlgorithms.graph;

    // DisjSetsFast class
    //
    // CONSTRUCTION: with int representing initial number of sets
    //
    // ******************PUBLIC OPERATIONS*********************
    // void union( root1, root2 ) --> Merge two sets
    // int find( x )              --> Return set containing x
    // ******************ERRORS********************************
    // No error checking is performed
    /**
    *@see 不相交集类
    * todo 路径压缩不完全与安高度求并的灵巧求并法完全兼容(但是与按大小求并完全兼容),因为路径压缩会改变(合并的两棵树高度相同时+1),无法有效的重新计算高度,所以“不计算”，此时:按秩求并(对于每棵树所存储的高度是"估计的高度"成为秩)
     * Disjoint set class, using union by rank
     * and path compression.
     * Elements in the set are numbered starting at 0.
     * @author Mark Allen Weiss
     *todo 按高度求并(本例!!!!!!)：--->改造成按大小求并与路径压缩方式只需要将root高度的值改为树的大小，以及求并时更新数的大小即可!!!!!!
     *todo 只有root处存储的才是负值，非root处仍然是是指向根，判断是否为根时仍然是<0!!
     *todo 由于零的高度不是负值(-0不是负值)，所以root处存储的是高度减一。
     *todo 按大小求并：
     *todo root处存储的是树的大小的负值，其他相同
     * */
    /*todo 路径压缩与灵巧求并法的结合*/
    public class DisjSetsFast
    {
        /**
         * Construct the disjoint sets object.
         * @param numElements the initial number of disjoint sets.
         *todo 基础结构都是数组
         */
        public DisjSetsFast( int numElements )
        {
            s = new int [ numElements ];
            for( int i = 0; i < s.length; i++ )
                s[ i ] = -1;
        }

        /**
         * Union two disjoint sets using the height heuristic.
         * For simplicity, we assume root1 and root2 are distinct
         * and represent set names.
         * @param root1 the root of set 1.
         * @param root2 the root of set 2.
         */
        public void union( int root1, int root2 )
        {
            if( s[ root2 ] < s[ root1 ] )  // root2 is deeper
                s[ root1 ] = root2;        // Make root2 new root
            else
            {
                if( s[ root1 ] == s[ root2 ] )
                    s[ root1 ]--;          // todo Update height if same 只有当两颗深度相等时的树合并时深度才会增加+1,实际存储中跟的数据 s[ root1 ]-- (代码的简洁!!!!!!)
                s[ root2 ] = root1;        //todo Make root1 new root :root1 is deeper root1更深和root1与root2一样深时，都是将root1的根赋给root2，只是相对于root1更深，一样深时多进行了一步深度更新操作，+1(存储中deep--)
            }
        }

        /**
         * Perform a find with path compression.
         * Error checks omitted again for simplicity.
         * @param x the element being searched for.
         * @return the set containing x.
         * todo 递归中，只有最后一个return x;因此，而且递归中没有对find()的返回值多做处理，所以，每一层递归的s[s]接收到的都是最后return的x。在层层
         */
        public int find( int x )
        {
            if( s[ x ] < 0 )
                return x;
            else
                /*todo 路径压缩: 从x到root的路径上的每一个节点使其父节点是本树的root(从x到root的路径上的每一个节点都直接指向root)*/
                /*todo 在集合的根被递归的找到以后，x的父链都引用了它。这对通向跟的路径上的每一个节点递归的出现*/
                return s[ x ] = find( s[ x ] );
        }

        private int [ ] s;


        // Test main; all finds on same output line should be identical
        public static void main( String [ ] args )
        {
            int NumElements = 128;
            int NumInSameSet = 16;

            DisjSetsFast ds = new DisjSetsFast( NumElements );
            int set1, set2;

            for( int k = 1; k < NumInSameSet; k *= 2 )
            {
                int i=0;
                for( int j = 0; j + k < NumElements; j += 2 * k,i++ )
                {
                    set1 = ds.find( j );
                    set2 = ds.find( j + k );
                    ds.union( set1, set2 );
                }
                System.out.println(i);
            }

            for( int i = 0; i < NumElements; i++ )
            {
                System.out.print( ds.find( i )+ "*" );
                if( i % NumInSameSet == NumInSameSet - 1 )
                    System.out.println( );
            }
            System.out.println( );
        }
    }
